package com.lw.leetcode.hash.c;

import java.util.HashSet;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * c
 * hash
 * 1923. 最长公共子路径
 * 滚动hash示例
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/11 18:06
 */
public class LongestCommonSubpath {

    public static void main(String[] args) {
        LongestCommonSubpath test = new LongestCommonSubpath();


        // 0
        int[][] arr = {{0, 1, 2, 3, 4}, {5}};
        int n = 5;

        // 1
//        int[][] arr = {{0, 1, 2, 3, 4}, {4, 3, 2, 1, 0}};
//        int n = 5;

        // 1
//        int[][] arr = {{1, 2, 3, 4}, {4, 1, 2, 3}, {4}};
//        int n = 5;

        // 2
//        int[][] arr = {{0, 1, 2, 3, 4}, {2, 3, 4}, {4, 0, 1, 2, 3}};
//        int n = 5;

        // 5
//        int[][] arr = {{2, 1, 4, 0, 3}, {2, 1, 4, 0, 3}};
//        int n = 10;

        //
//        int[][] arr = Utils.getArr(2, 50000, 0, 30);
//        int n = 100000;
//
//        for (int[] ints : arr) {
//            for (int i = 1; i < ints.length; i++) {
//                if (ints[i] == ints[i - 1]) {
//                    ints[i] += 3000;
//                }
//            }
//        }
//        System.out.println(n);
//        Utils.toPrint(arr);

        int i = test.longestCommonSubpath(n, arr);
        System.out.println(i);

    }

    private int m1 = 1000000007;
    private int m2 = 1000000009;
    private int b1;
    private int b2;
    private Set<Long> alls = new HashSet<>();
    private Set<Long> items = new HashSet<>();

    public int longestCommonSubpath(int n, int[][] paths) {
        int end = paths[0].length;
        for (int[] path : paths) {
            end = Math.min(end, path.length);
        }
        b1 = (int) (Math.random() * (1000000 - 100000) + 100000);
        b2 = (int) (Math.random() * (1000000 - 100000) + 100000);
        int st = 0;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            alls.clear();
            if (find(paths, m)) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        return st;
    }

    private boolean find(int[][] paths, int m) {
        add(paths[0], alls, m);
        if (alls.isEmpty()) {
            return false;
        }
        for (int i = paths.length - 1; i > 0; i--) {
            items.clear();
            add(paths[i], items, m);
            alls.retainAll(items);
            if (alls.isEmpty()) {
                return false;
            }
        }
        return true;
    }

    private void add(int[] arr, Set<Long> set, int m) {
        int length = arr.length;
        if (length < m) {
            return;
        }
        long item1 = 0;
        long item2 = 0;
        long g1 = 1;
        long g2 = 1;
        for (int i = 0; i < m; i++) {
            int t = arr[i];
            item1 = (item1 * b1 + t) % m1;
            item2 = (item2 * b2 + t) % m2;
            g1 = (g1 * b1) % m1;
            g2 = (g2 * b2) % m2;
        }
        set.add((item1 << 32) + item2);
        for (int i = m; i < length; i++) {
            int t = arr[i];
            item1 = (item1 * b1 + t) % m1;
            item2 = (item2 * b2 + t) % m2;
            int t1 = arr[i - m];
            item1 = (item1 - t1 * g1) % m1;
            item1 = item1 < 0 ? item1 + m1 : item1;
            item2 = (item2 - t1 * g2) % m2;
            item2 = item2 < 0 ? item2 + m2 : item2;
            set.add((item1 << 32) + item2);
        }
    }

}
